/*
 * @lc app=leetcode.cn id=207 lang=typescript
 *
 * [207] 课程表
 */

// @lc code=start
function canFinish(numCourses: number, prerequisites: number[][]): boolean {
  const graph: number[][] = new Array(numCourses).fill(0).map(() => []);
  const degree = new Array(numCourses).fill(0);

  // 建模
  for (let [to, from] of prerequisites) {
    graph[from].push(to);
    degree[to] += 1;
  }
  // 将入度为0的放入队列
  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (degree[i] === 0) queue.push(i);
  }

  const result = [];
  // 每次取出队首元素，将元素放入结果
  // 同时将当前元素对应边的入度减1，并将入度为0的放入队尾
  while (queue.length) {
    const idx = queue.shift();
    result.push(idx);
    for (let to of graph[idx]) {
      degree[to] -= 1;
      if (degree[to] === 0) queue.push(to);
    }
  }
  // 最后的结果就是拓扑排序，判断是否跟课程数量一致即可
  return result.length === numCourses;
}
// @lc code=end
